#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 定义多项式项的结构体
struct PolyTerm {
    int coef; // 系数
    int exp; // 指数
    PolyTerm(int c, int e) : coef(c), exp(e) {}
};

// 定义单链表节点的结构体
struct PolyNode {
    PolyTerm term; // 多项式项
    PolyNode* next; // 指向下一个节点的指针
    PolyNode(PolyTerm t) : term(t), next(nullptr) {}
};

// 定义单链表的类
class PolyList {
public:
    PolyList() : head(nullptr) {}
    ~PolyList() {
        PolyNode* p = head;
        while (p) {
            PolyNode* temp = p;
            p = p->next;
            delete temp;
        }
    }

    // 在链表尾部插入多项式项
    void insert(PolyTerm t) {
        PolyNode* p = new PolyNode(t);
        if (head == nullptr) {
            head = p;
        } else {
            PolyNode* cur = head;
            while (cur->next != nullptr) {
                cur = cur->next;
            }
            cur->next = p;
        }
    }

    // 打印链表中的多项式项
    void print() {
        PolyNode* p = head;
        while (p) {
            cout << p->term.coef << "x^" << p->term.exp << " ";
            p = p->next;
        }
        cout << endl;
    }

    // 两个多项式相乘
    PolyList* multiply(PolyList& other) {
        PolyList* result = new PolyList();
        PolyNode* p = head;
        PolyNode* q = other.head;
        while (p && q) {
            PolyTerm t = {p->term.coef * q->term.coef, p->term.exp + q->term.exp};
            result->insert(t);
            p = p->next;
            q = q->next;
        }
        return result;
    }
private:
    PolyNode* head;
};

int main() {
    PolyList pl1, pl2;
    PolyTerm t1 = {1, 1};
    PolyTerm t2 = {2, 0};
    PolyTerm t3 = {3, 1};
    PolyTerm t4 = {4, 2};
    PolyTerm t5 = {5, 0};
    PolyTerm t6 = {6, 1};

    pl1.insert(t1);
    pl1.insert(t2);
    pl1.insert(t3);
    pl1.insert(t4);

    pl2.insert(t5);
    pl2.insert(t6);

    cout << "多项式 pl1: ";
    pl1.print();

    cout << "多项式 pl2: ";
    pl2.print();

    PolyList* result = pl1.multiply(pl2);

    cout << "乘积多项式: ";
    result->print();

    delete result;

    return 0;
}
